package demo07String;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User:咭咭熊
 * Date:2021 - 10 - 19
 * Time:16:30
 */

/***
 * KMP算法主要解决：在字符串中的模式定位问题【即关键字搜索】
 * 模式串就是关键字P，如果它在一个主串T中出现，就返回它的具体位置;否则返回-1
 */
public class KMP {

    /***
     * 2.KMP算法：
     * 利用已经部分匹配这个有效信息，保持i指针不会苏，通过修改j指针，让模式串尽量的移动到有效的位置
     * 当匹配失败时，j要移动的下一个位置k:最前面的k个字符和j之前的最后k个字符相同
     * @param ts
     * @param ps
     * @return
     */
    public static int KMP(String ts,String ps){
        char[] t = ts.toCharArray();
        char[] p = ps.toCharArray();
        int i = 0;//主串的位置
        int j = 0;//模式串的位置
        int[] next = getNext(ps);
        while(i < t.length && j < p.length) {
            if (j == -1 || t[i] == p[j]) {
                i++;
                j++;
            } else {
                //i不需要回溯了
                j = next[j];//j回到指定位置
            }
        }
        if(j == p.length){
            return i - j;
        }else{
            return -1;
        }

    }

    public static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while (j < p.length - 1) {
            if (k == -1 || p[j] == p[k]) {
                if (p[++j] == p[++k]) { // 当两个字符相等时要跳过
                    next[j] = next[k];
                } else {
                    next[j] = k;
                }
            } else {
                k = next[k];
            }
        }
        return next;
    }
/*    //找到k的位置
    private static int[] getNext(String ps) {
        char[] p = ps.toCharArray();
        int[] next = new int[p.length];
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j <p.length - 1){
            if(k == -1 || p[j] == p[k]){
                next[++j] = ++k;
            }else{
                k = next[j];
            }
        }
        return next;
    }*/

    /***
     * 1.暴力破解法
     * 从左到右一个个匹配，如果此过程中有某个字符不匹配，就跳回去，将模式串右移一位，再次比较
     * @param sour  主串
     * @param tar  模式串
     * @return  如果找到，返回在主串中第一个字符出现的下标，否为返回-1
     */
    public static int bf(String sour,String tar){
        char[] s = sour.toCharArray();
        char[] t = tar.toCharArray();
        int i = 0;//主串的位置
        int j = 0;//模式串的位置
        while(i < s.length && j <t.length){
            if(s[i] == t[j]){//当两个字符相同
                i++;
                j++;
            }else{
                //一旦不匹配，i后退，j= 0
                i = i - j + 1;
                j = 0;
            }
        }
        if(j == t.length){
            return i - j;
        }else{
            return -1;
        }
    }
}
